/**
 * 
 */
package datamodel.tree;

import java.util.ArrayList;
import java.util.List;

/**
 * The abstract class for a tree.
 * 
 * @author Kevin Munk, Jakob Karolus
 * @version 1.0
 * 
 */
public abstract class Tree {

	/**
	 * Moves to the left child of the current node
	 * 
	 * @return true if left child exists and the move was successful; otherwise
	 *         false
	 */
	public abstract boolean moveToLeftNode();

	/**
	 * Moves to the right child of the current node
	 * 
	 * @return true if right child exists and the move was successful; otherwise
	 *         false
	 */
	public abstract boolean moveToRightNode();

	/**
	 * Moves to the parent of the current node
	 * 
	 * @return true if parent exists and the move was successful; otherwise
	 *         false
	 */
	public abstract boolean moveToParentNode();

	/**
	 * @return true if left child exists; otherwise false
	 */
	public abstract boolean hasLeftNode();

	/**
	 * @return true if right child exists; otherwise false
	 */
	public abstract boolean hasRightNode();

	/**
	 * @return true if parent exists; otherwise false
	 */
	public abstract boolean hasParentNode();

	/**
	 * Sets the left child of the current node
	 * 
	 * @return true if successful; otherwise false (no root set)
	 * 
	 */
	public abstract boolean setLeftNode(TreeNode node);

	/**
	 * Sets the right child of the current node
	 * 
	 * @return true if successful; otherwise false (no root set)
	 * 
	 */
	public abstract boolean setRightNode(TreeNode node);

	/**
	 * Sets the current node. If the tree is empty, sets the root.
	 * 
	 */
	public abstract void setCurrentNode(TreeNode node);

	/**
	 * @return the current node or null if the tree is empty
	 */
	public abstract TreeNode getCurrentNode();

	/**
	 * moves to the root node of this tree
	 * 
	 * @return true if there's a root; otherwise false
	 */
	public abstract boolean moveToRoot();

	/**
	 * clears the whole tree, which includes deleting all nodes and the root
	 * node
	 */
	public abstract void clearTree();
	
	
	@Override
	public boolean equals(Object object){
		if(!(object instanceof Tree)) {
			return false;
		}
		
		Tree tree = (Tree) object;
		List<TreeNode> visited = new ArrayList<TreeNode>();
		
		// Wurzel
		this.moveToRoot();
		tree.moveToRoot();
		TreeNode rootA = this.getCurrentNode();
		
		if(!tree.getCurrentNode().equals(rootA)) {
			return false;
		}

		// Vergleich der beiden Bäume miteinander.
		boolean compare = true;
		while(compare) {

			// linker rechter Knoten wird bestimmt
			TreeNode leftNode = null;
			if(this.hasLeftNode()) {
				this.moveToLeftNode();
				leftNode = this.getCurrentNode();
				this.moveToParentNode();
			}

			TreeNode rightNode = null;
			if(this.hasRightNode()) {
				this.moveToRightNode();
				rightNode = this.getCurrentNode();
				this.moveToParentNode();
			}
			
			///////////////////////////////////////////////////////////
			// Der eigentliche Vergleich:
			// Es wird solange nach links gegangen bis es nicht mehr geht und 
			// vergleicht die Knoten anschließend.
			// Man geht eine Ebene höher und versucht 1 mal nach rechts zu gegen um 
			// dann wieder solange nach links bis es nicht mehr geht.
			// Sind sowohl linkes als auch rechtes Kind besucht geht man eine Ebene 
			// zurück und versucht dann einmal nach rechts zu gehen.
			// Ist man bei der Wurzel angekommen und versucht weiter nach oben zu gehen 
			// sind beide Bäume gleich. 
			///////////////////////////////////////////////////////////
			if(this.hasLeftNode() && tree.hasLeftNode() && visited.contains(leftNode)) {
				this.moveToLeftNode();
				tree.moveToLeftNode();
				
				if(!this.getCurrentNode().equals(tree.getCurrentNode())) {
					return false;
				} else visited.add(this.getCurrentNode());
			}
			else if(this.hasRightNode() && tree.hasRightNode() && visited.contains(rightNode)) {
				this.moveToRightNode();
				tree.moveToRightNode();
				
				if(!this.getCurrentNode().equals(tree.getCurrentNode())) {
					return false;
				} else visited.add(this.getCurrentNode());	
			}
			else if(!this.hasLeftNode() && !tree.hasLeftNode() ||
					!this.hasRightNode() && !tree.hasRightNode()){
				this.moveToParentNode();
				tree.moveToParentNode();
			}
			else if(!tree.moveToParentNode()) {
				return true;
			}
			else return false;
		}
		return false;
	}
}
